package leetcode;

import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * Leetcode503【下一个更大元素 II】
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 */
//单调栈解
public class NextGreaterElementsTwoFunTwo {
    private int[] ret;
    private Stack<Integer> stack = new Stack<>();//存放下一个更大元素的索引栈
    public int[] nextGreaterElements(int[] nums) {
        ret = new int[nums.length];
        Arrays.fill(ret , -1);
        for (int i = 0; i < 2 * nums.length - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % nums.length]){
                ret[stack.pop()] = nums[i % nums.length];
            }
            stack.push(i % nums.length);
        }
        return ret;
    }
}
